Gerichtete Graphen mit SQL lösen – Teil 2

Im ersten Teil dieses Artikels ging es um die Verwendung von SQL zur Lösung von Problemen mit gerichteten Graphen. Eine weitere Art gerichteter Graphen ist eine Zustandsmaschine. Bei einer Zustandsmaschine wird jeder Knoten ‚Zustand‘ genannt und repräsentiert den aktuellen Status eines Systems, eines Objekts oder einer Variablen. Zwischen den einzelnen Zuständen entstehen Vektoren, welche die durch externe Ereignisse verursachten Zustandsänderungen repräsentieren.

So beruhen zum Beispiel die Ereignis-basierte Architektur von Windows oder die JavaScript-Ereignisse auf der Idee, eine grafische Benutzeroberfläche mit einer Menge von Objekten zu versehen, die auf unterschiedliche ‚Ereignisse‘ (durch Benutzereingaben oder das System ausgelöst) reagieren.

Selbst der Compiler einer Programmiersprache ist eine Zustandsmaschine. Ein Compiler erkennt einzelne Token, indem er zwischen unterschiedlichen Zuständen wechselt, bis ein Token ‚erkannt‘ ist. Ein beliebtes Utility – lex – wird häufig verwendet, um eine Menge von Token (reservierten Wörtern) in eine Zustandsmaschine in C zu konvertieren und zu optimieren. Denselben Prozess kann man auch mit SQL ausführen – mit einem entscheidenden Vorteil: der generierte Code kann in jeder beliebigen Sprache vorliegen.

Zuerst wird eine eine Tabelle mit Token erstellt:

Eine Zustandsmaschine muss eine Menge von Zuständen (states) sowie die Menge der Übergänge (transitions) zwischen den einzelnen Zuständen speichern. Im folgenden Beispiel wird jeder Übergang durch ein einzelnes eingegebenes Zeichen repräsentiert.